package jianzhi

func fib1(n int) int {

	var mod int = 1e9 + 7

	if n == 1 || n == 2 {
		return 1
	} else if n < 1 {
		return 0
	}

	p, q, res := 1, 1, 0

	for i := 3; i <= n; i++ {
		res = (p + q) % mod
		p = q
		q = res
	}

	return res
}

type FiboNode struct {
	n   int
	tag int // 1 左 2右
}

func fibo_stack(n int) int {

	stack := []FiboNode{}
	var w FiboNode
	sum := 0

	for {

		for n > 1 {
			w.n = n
			w.tag = 1
			stack = append(stack, w)
			n--
		}
		sum += n
		for len(stack) != 0 {
			w = stack[len(stack)-1]
			stack = stack[:len(stack)-1] // 出栈
			if w.tag == 1 {              // 遇到左子树，放到右边去
				w.tag = 2
				stack = append(stack, w)
				n = w.n - 2
				break
			}
		}
		if len(stack) == 0 {
			break
		}
	}
	return sum
}
